package work.xiaohong.arithmetic.SortArithmetic;

/**
 * @author xiaohong
 * @version 1.0
 * @date 2021/10/26 0026 9:35
 * @description 快速排序
 */
public class Quick {

    /**
     * 排序原理
     * 1.首先设定一个分界值，通过该分界值将数组分成左右两部分;
     * 2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值;
     * 3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
     * 4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。
     *
     * 时间复杂度
     * 最优情况
     * O(nlogn)
     * 最坏情况
     * O(n2)
     * 不稳定的排序算法
     */

    // 对数组内的元素进行排序
    public static void quickSort(Comparable[] arr){
        int lo = 0;
        int hi = arr.length-1;
        sort(arr,lo,hi);
    }

    // 对数组索引lo到hi之间的元素进行排序
    private static void sort(Comparable[] arr, int lo, int hi) {
        // 安全性校验
        if (hi <= lo){
            return;
        }

        // 需要对数组lo到hi索引的元素进行分组（左子组和右子组） 返回的是分组的分界值所在的索引，分界值位置
        int partition = partition(arr,lo,hi);

        // 让左子组排序
        sort(arr,lo,partition-1);

        // 让右子组排序
        sort(arr,partition+1,hi);

    }

    private static int partition(Comparable[] arr, int lo, int hi) {
        // 确定分界值
        Comparable key = arr[lo];

        // 定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置
        int left = lo;
        int right = hi+1;

        // 切分
        while (true){
            // 先从右往左扫描，移动right指针，找到一个比分界值小的元素才停止
            while (SortUtils.greater(arr[--right],key)){
                if (right == lo){
                    break;
                }
            }

            // 再从左往右扫描，移动left指针，找到一个比分界值大的元素才停止
            while (SortUtils.greater(key,arr[++left])){
                if (right == lo){
                    break;
                }
            }

            // 判断left>=right 如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可
            if (left >= right){
                break;
            }else {
                SortUtils.swap(arr,left,right);
            }
        }

        // 交换分界值
        SortUtils.swap(arr,lo,right);

        // 返回交换后分界值的下标索引
        return right;

    }


}
